// 选择k个数字使得两集合累加和相差不超过1
// 给定一个正数n，表示1~n这些数字都可以选择
// 给定一个正数k，表示要从1~n中选择k个数字组成集合A，剩下数字组成集合B
// 希望做到集合A和集合B的累加和相差不超过1
// 如果能做到，返回集合A选择了哪些数字，任何一种方案都可以
// 如果不能做到，返回长度为0的数组
// 2 <= n <= 10^6
// 1 <= k <= n
// 来自真实大厂笔试，没有测试链接，用对数器验证

#include <bits/stdc++.h>

using namespace std;

// 1 ~ n这些数字挑选k个
// 能不能凑够累加和sum
// 能的话，返回挑选了哪些数字
// 不能的话，返回长度为0的数组
vector<int> generate(long sum, int n, int k)
{
    long minKSum = (k + 1) * k / 2;
    int range = n - k;
    if(sum < minKSum || sum > minKSum + (long)range * k) return {};

    /*
    n = 30, k = 5
    情况一、 minKsum = 15, sum = 100, need = 85
            range = 25, rightSize = 3
            midIndex = 12, leftSize = 1
            1 12 28 29 30
    
    情况二、 minKsum = 15, sum = 90, need = 75
            range = 25, rightSize = 3
            midIndex = 2, leftSize = 2
            1 2 28 29 30
    */
    long need = sum - minKSum;
    int rightSize = need / range;
    int midIndex = k - rightSize + (need % range);
    int leftSize = k - rightSize - (need % range == 0 ? 0 : 1);
    vector<int> ans(k);
    // 左边的部分
    for(int i = 0; i < leftSize; ++i) ans[i] = i + 1;
    // 中间的部分
    if(need % range != 0) ans[leftSize] = midIndex;
    // 右边的部分
    for(int i = k - 1, j = 0; j < rightSize; --i, ++j)
    {
        ans[i] = n - j;
    }
    return ans;
}

bool f(int n, int i, int k, long s, vector<vector<vector<int>>>& dp)
{
    if(k < 0 || s < 0) return false;
    if(i == n + 1) return k == 0 && s == 0;
    if(dp[i][k][s] != 0) return dp[i][k][s] == 1;
    bool ans = f(n, i + 1, k, s, dp) || f(n, i + 1, k - 1, s - i, dp);
    dp[i][k][s] = ans ? 1 : -1;
    return ans;
}

// 记忆化搜索
// 不是最优解，只是为了验证
// 返回能不能做到
bool canSplit(int n, int k)
{
    long sum = (n + 1) * n / 2;
    long wantSum = sum / 2 + ((sum & 1) == 0 ? 0 : 1);
    vector<vector<vector<int>>> dp(n + 1, vector<vector<int>>(k + 1, vector<int>(wantSum + 1)));
    return f(n, 1, k, wantSum, dp);
}

// 为了验证
// 检验得到的结果是否正确
bool pass(int n, int k, vector<int>& ans)
{
    if(ans.size() == 0)
    {
        if(canSplit(n, k)) return false;
        else return true;
    }
    else
    {
        if(ans.size() != k) return false;
        long sum = (n + 1) * n / 2;
        int pickSum = 0;
        for(int num : ans) pickSum += num;
        return abs(pickSum - (sum - pickSum)) <= 1;
    }
}

// 正式方法
// 最优解
vector<int> pick(int n, int k)
{
    long sum = (n + 1) * n / 2;
    vector<int> ans = generate(sum / 2, n, k);
    if(ans.size() == 0 && (sum & 1) == 1)
    {
        ans = generate(sum / 2 + 1, n, k);
    }
    return ans;
}

int main()
{
    // 为了验证
	// 对数器
    srand(time(nullptr));
    int N = 60;
    int testTime = 5000;
    cout << "测试开始" << endl;
    for(int i = 0; i < testTime; ++i)
    {
        int n = rand() % N + 2;
        int k = rand() % n + 1;
        vector<int> ans = pick(n, k);
        if(!pass(n, k, ans)) cout << "出错了" << endl;
    }
    cout << "测试结束" << endl;

    return 0;
}